package disjointsets;

import java.util.*;

/**
 * @BelongsProject: Leetcode
 * @BelongsPackage: disjointsets
 * @Author: Vazh
 * @CreateTime: 2021/5/7 22:54
 * @Description: 账户合并
 * 给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
 *
 * 现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
 *
 * 合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按字符 ASCII 顺序排列的邮箱地址。账户本身可以以任意顺序返回。
 *
 *
 *
 * 示例 1：
 *
 * 输入：
 * accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
 * 输出：
 * [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
 * 解释：
 * 第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "johnsmith@mail.com"。
 * 第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
 * 可以以任何顺序返回这些列表，例如答案 [['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
 * ['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']] 也是正确的。
 *
 *
 * 提示：
 *
 * accounts的长度将在[1，1000]的范围内。
 * accounts[i]的长度将在[1，10]的范围内。
 * accounts[i][j]的长度将在[1，30]的范围内。
 */
public class Leetcode721 {

    // 利用一个字符串的映射存储并查集
    Map<String, String> q;
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        q = new HashMap<>();
        // 这个映射存储每个邮箱对应账户的名字
        Map<String, String> names = new HashMap<>();

        // 遍历所有账户构建并查集
        for(List<String> a : accounts) {
            for(int i = 1; i < a.size(); i++) {
                if(!q.containsKey(a.get(i))){
                    // 如果并查集中没有这个邮箱，则添加邮箱，其根元素就是本身
                    q.put(a.get(i), a.get(i));
                    // 添加该邮箱对应的账户名
                    names.put(a.get(i), a.get(0));
                }

                if(i > 1) {
                    // 并查集的合并操作，合并一个账户中的所有邮箱
                    q.put(find(a.get(i)), find(a.get(i - 1)));
                }
            }
        }

        // 暂时存储答案中的邮箱列表，每个键值对的键就是每个并查集集合的根元素
        Map<String, List<String>> temp = new HashMap<>();
        for(String email : q.keySet()) {
            // 获取当前邮箱对应并查集的根元素
            String root = find(email);
            // 将当前邮箱放入根元素对应的列表中
            if(!temp.containsKey(root)) temp.put(root, new ArrayList<>());
            temp.get(root).add(email);
        }

        // 将答案从映射中放到列表
        List<List<String>> res = new ArrayList();
        for(String root : temp.keySet()) {
            // 获取当前根元素对应的列表
            List<String> layer = temp.get(root);
            // 题目要求的排序
            Collections.sort(layer);
            // 添加姓名
            layer.add(0, names.get(root));
            // 将当前列表加入答案
            res.add(layer);
        }

        return res;
    }

    // 并查集查找模板函数，这里用字符串替换了之前的整型
    // find就是一个寻根归祖的方法，寻找当前元素最终将属于哪个根元素，这个根元素来表示一个联通集合
    // 如果x映射的值等于x，那就可以说明x是个根元素，例如一个集合中只有一个元素，那么它当然可以代表自己
    // 这样做可以让一个集合中的所有元素都能直接或者间接指向根元素，一个集合中只有一个元素的映射是本身
    private String find(String x) {
        // 判断x是不是就是一个根元素
        if(!q.get(x).equals(x)) {
            // x不是根，那就通过递归find函数来找到x映射的元素的根元素（寻根）
            // 找到根元素之后，通过put方法将x直接映射到根元素，这样就免去中间的多次递归（归祖）
            q.put(x, find(q.get(x)));
        }

        // 最终，x映射的元素就是x所在的集合的根元素，返回x的根元素
        return q.get(x);
    }
}
